package leetcode_1_200;

import java.util.HashMap;
import java.util.Map;

public class LeeCode_105 {
    public static void main(String[] args) {
//        TreeNode treeNode = buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
//        TreeNode treeNode2 = buildTree(new int[]{-1}, new int[]{-1});
//        TreeNode treeNode3 = buildTree(new int[]{1,2}, new int[]{2,1});
//        TreeNode treeNode4 = buildTree(new int[]{1,2}, new int[]{1,2});
//        TreeNode treeNode5 = buildTree(new int[]{1,2,3}, new int[]{1,2,3});
//        TreeNode treeNode5 = buildTree(new int[]{1,2,3}, new int[]{3,2,1});
        TreeNode treeNode5 = buildTree(new int[]{1,2,3,4}, new int[]{1,2,3,4});
    }

    private static TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> imap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++)
            imap.put(inorder[i], i);
        TreeNode root = new TreeNode(preorder[0]);
        return f(0, preorder, inorder, imap, 0, preorder.length - 1);
    }
    private static TreeNode f(int now, int[] preorder, int[] inorder,
                              Map<Integer, Integer> imap, int s, int e){
        if (s == e)
            return new TreeNode(inorder[s]);
        if (now >= preorder.length || s > e){
            return null;
        }
        int mid = imap.get(preorder[now]);
        int lc = mid - s;
        int rc = e - mid;
        TreeNode l = f(now + (lc > 0 ? 1 : 0), preorder, inorder, imap, s, mid - 1);
        TreeNode r = f(now + lc + (rc > 0 ? 1 : 0), preorder, inorder, imap, mid + 1, e);
        return new TreeNode(preorder[now], l, r);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
